﻿package rpg.Utils
{
	import flash.utils.getTimer;

	/**
	 * A* 寻路算法
	 */
	public class AStar
	{
		public static var walkableNum : int = 127;
		public static var unwalkableNum : int = 0;
		//====================================
		//	Constants
		//====================================
		//横或竖向移动一格的路径评分
		private const COST_STRAIGHT : int = 10;

		//斜向移动一格的路径评分
		private const COST_DIAGONAL : int = 14;

		//(单个)节点数组 节点ID 索引
		private const NOTE_ID : int = 0;

		//(单个)节点数组 是否在开启列表中 索引
		private const NOTE_OPEN : int = 1;

		//(单个)节点数组 是否在关闭列表中 索引
		private const NOTE_CLOSED : int = 2;

		//====================================
		//	Member Variables
		//====================================
		//最大寻路步数，限制超时返回
		private var m_maxTry : int;

		//开放列表，存放节点ID
		private var m_openList : Vector.<int> = new Vector.<int>();

		//开放列表长度
		private var m_openCount : int;

		//节点加入开放列表时分配的唯一ID(从0开始)
		//根据此ID(从下面的列表中)存取节点数据
		private var m_openId : int;

		//节点x坐标列表
		private var m_xList : Vector.<int> = new Vector.<int>();

		//节点y坐标列表
		private var m_yList : Vector.<int> = new Vector.<int>();


		//节点路径评分列表F
		private var m_pathScoreList : Vector.<int> = new Vector.<int>();

		//(从起点移动到)节点的移动耗费列表G
		private var m_movementCostList : Vector.<int> = new Vector.<int>();

		//节点的父节点(ID)列表
		private var m_fatherList : Vector.<int> = new Vector.<int>();

		//节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID
		private var m_noteMap : Array = [];

		private var _mapBlocks : Array = [];

		private var _mapBlockRows : int;

		private var _mapBlockColums : int;

		/**
		 * 格子的宽度
		 */
		private var titleWidth : int;
		/**
		 * 格子的告诉
		 */
		private var titleHeight : int;

		private static var instance : AStar;


		//====================================
		//	Constructor
		//====================================
		public static function getInstance() : AStar
		{
			if(instance == null)
				instance = new AStar();
			return instance;
		}

		public function init(mapBlocks : Array , p_maxTry : int = 2000) : void
		{
			_mapBlocks = mapBlocks;
			if(_mapBlocks == null)
			{
				Log.warning("不能传入空地图数据");
				return;
			}
			this.m_maxTry = p_maxTry;

			_mapBlockRows = _mapBlocks.length;
			_mapBlockColums = _mapBlocks[0].length;

			titleWidth = GameUtils.GRID_WIDTH;
			titleHeight = GameUtils.GRID_HEIGHT;
		}

		public function AStar()
		{

		}

		//====================================
		//	Properties
		//====================================
		/**
		 * 最大寻路步数，限制超时返回
		 */
		public function get maxTry() : int
		{
			return this.m_maxTry;
		}

		/**
		 * @private
		 */
		public function set maxTry(p_value : int) : void
		{
			this.m_maxTry = p_value;
		}

		/**
		 * 开始寻路 ,如果两点有无效的点则先将两点转化为附近的有效点再进行寻路
		 * @param startIndexX
		 * @param startIndexY
		 * @param endIndexX
		 * @param endIndexY
		 * @return
		 *
		 */
		public function findByAvaliabePoint(startIndexX : int , startIndexY : int , endIndexX : int , endIndexY : int) : Array
		{
			var avaliableStart : Array = AStar.getInstance().getAvailablePoint(startIndexX , startIndexY , endIndexX , endIndexY);
			var avaliableEnd : Array = AStar.getInstance().getAvailablePoint(endIndexX , endIndexY , startIndexX , startIndexY);

			var paths : Array = find(avaliableStart[0] , avaliableStart[1] , avaliableEnd[0] , avaliableEnd[1]);
			return paths;
		}

		/**
		 * 开始寻路
		 *
		 * @param p_startX		起点X坐标
		 * @param p_startY		起点Y坐标
		 * @param p_endX		终点X坐标
		 * @param p_endY		终点Y坐标
		 *
		 * @return 				找到的路径(二维数组 : [p_startX, p_startY], ... , [p_endX, p_endY])
		 */
		public function find(p_startX : int , p_startY : int , p_endX : int , p_endY : int) : Array
		{
			if(_mapBlocks == null)
				return null;

			if(isBlock(p_endX , p_endY))
				return null;
			//初始化数组
			this.initLists();
			this.m_openCount = 0;
			this.m_openId = -1;

			//添加起始点到开启列表
			this.openNote(p_startX , p_startY , 0 , 0 , 0);

			var currTry : int = 0;
			var currId : int;
			var currNoteX : int;
			var currNoteY : int;
			var aroundNotes : Array;

			var checkingId : int;

			var cost : int;
			var score : int;
			while(this.m_openCount > 0)
			{
				//超时返回
				if(++currTry > this.m_maxTry)
				{
					this.destroyLists();
					return null;
				}
				//每次取出开放列表最前面的ID
				currId = this.m_openList[0];
				//将编码为此ID的元素列入关闭列表
				this.closeNote(currId);
				currNoteX = this.m_xList[currId];
				currNoteY = this.m_yList[currId];

				//如果终点被放入关闭列表寻路结束，返回路径
				if(currNoteX == p_endX && currNoteY == p_endY)
				{
					return this.getPath(p_startX , p_startY , currId);
				}
				//获取周围节点，排除不可通过和已在关闭列表中的
				aroundNotes = this.getArounds(currNoteX , currNoteY);
//				if(aroundNotes == null || aroundNotes.length == 0)
//				{//死路
//					break;
//				}

				//对于周围的每一个节点
				for each(var note : Array in aroundNotes)
				{
					//计算F和G值 cost 为G,score 为f
					cost = this.m_movementCostList[currId] + ((note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL);
					score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
					if(this.isOpen(note[0] , note[1])) //如果节点已在播放列表中
					{
						checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
						//如果新的G值比节点原来的G值小,修改F,G值，换父节点
						if(cost < this.m_movementCostList[checkingId])
						{
							//G值
							this.m_movementCostList[checkingId] = cost;
							//F值
							this.m_pathScoreList[checkingId] = score;
							this.m_fatherList[checkingId] = currId;
							this.aheadNote(this.getIndex(checkingId));
						}
					}
					else //如果节点不在开放列表中
					{
						//将节点放入开放列表
						this.openNote(note[0] , note[1] , score , cost , currId);
					}
				}
			}
			//清空所有数组
			this.destroyLists();
			return null;
		}

		/**
		 * 是否为障碍
		 * @param p_startX	始点X坐标
		 * @param p_startY	始点Y坐标
		 * @param p_endX	终点X坐标
		 * @param p_endY	终点Y坐标
		 * @return 0为障碍 1为通路
		 */
		public function isBlock(checkX : int , checkY : int) : Boolean
		{
			if(checkX < 0 || checkX >= _mapBlockColums || checkY < 0 || checkY >= _mapBlockRows)
			{
				return true;
			}
			return _mapBlocks[checkY][checkX] == unwalkableNum;
		}

		//====================================
		//	Private Methods
		//====================================
		/**
		 * @private
		 * 将节点加入开放列表
		 *
		 * @param p_x		节点在地图中的x坐标
		 * @param p_y		节点在地图中的y坐标
		 * @param P_score	节点的路径评分
		 * @param p_cost	起始点到节点的移动成本
		 * @param p_fatherId	父节点
		 */
		private function openNote(p_x : int , p_y : int , p_score : int , p_cost : int , p_fatherId : int) : void
		{
			this.m_openCount++; //初始为0
			this.m_openId++; //初始为-1

			if(this.m_noteMap[p_y] == null)
			{
				this.m_noteMap[p_y] = [];
			}
			this.m_noteMap[p_y][p_x] = [];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = true;
			//保存某节点的 在开启列表中索引的位置
			this.m_noteMap[p_y][p_x][NOTE_ID] = this.m_openId;

			this.m_xList.push(p_x);
			this.m_yList.push(p_y);
			//评分
			this.m_pathScoreList.push(p_score);
			this.m_movementCostList.push(p_cost);
			this.m_fatherList.push(p_fatherId);
			//id从0开始，count从-1开始
			this.m_openList.push(this.m_openId);
			this.aheadNote(this.m_openCount);
		}

		/**
		 * @private
		 * 将节点加入关闭列表
		 */
		private function closeNote(p_id : int) : void
		{
			this.m_openCount--;
			var noteX : int = this.m_xList[p_id];
			var noteY : int = this.m_yList[p_id];
			this.m_noteMap[noteY][noteX][NOTE_OPEN] = false;
			this.m_noteMap[noteY][noteX][NOTE_CLOSED] = true;

			if(this.m_openCount <= 0)
			{
				this.m_openCount = 0;
				this.m_openList = new Vector.<int>();
				return;
			}
			this.m_openList[0] = this.m_openList.pop();
			this.backNote();
		}

		/**
		 * @private
		 * 将(新加入开放别表或修改了路径评分的)节点向前移动
		 * @p_index  添加到开启列表的计数
		 */
		private function aheadNote(p_index : int) : void
		{
			var father : int;
			var change : int;
			while(p_index > 1)
			{
				//父节点的位置
				father = Math.floor(p_index / 2);
				//如果该节点的F值小于父节点的F值则和父节点交换
				if(this.getScore(p_index) < this.getScore(father))
				{
					change = this.m_openList[p_index - 1];
					this.m_openList[p_index - 1] = this.m_openList[father - 1];
					this.m_openList[father - 1] = change;
					p_index = father;
				}
				else
				{
					break;
				}
			}
		}

		/**
		 * @private
		 * 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动
		 */
		private function backNote() : void
		{
			//尾部的节点被移到最前面
			var checkIndex : int = 1;
			var tmp : int;
			var change : int;

			while(true)
			{
				tmp = checkIndex;
				//如果有子节点
				if(2 * tmp <= this.m_openCount)
				{
					//如果子节点的F值更小
					if(this.getScore(checkIndex) > this.getScore(2 * tmp))
					{
						//记节点的新位置为子节点位置
						checkIndex = 2 * tmp;
					}
					//如果有两个子节点
					if(2 * tmp + 1 <= this.m_openCount)
					{
						//如果第二个子节点F值更小
						if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
						{
							//更新节点新位置为第二个子节点位置
							checkIndex = 2 * tmp + 1;
						}
					}
				}
				//如果节点位置没有更新结束排序
				if(tmp == checkIndex)
				{
					break;
				}
				//反之和新位置交换，继续和新位置的子节点比较F值
				else
				{
					change = this.m_openList[tmp - 1];
					this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
					this.m_openList[checkIndex - 1] = change;
				}
			}
		}

		/**
		 * @private
		 * 判断某节点是否在开放列表
		 */
		private function isOpen(p_x : int , p_y : int) : Boolean
		{
			if(this.m_noteMap[p_y] == null)
				return false;
			if(this.m_noteMap[p_y][p_x] == null)
				return false;
			return this.m_noteMap[p_y][p_x][NOTE_OPEN];
		}

		/**
		 * @private
		 * 判断某节点是否在关闭列表中
		 */
		private function isClosed(p_x : int , p_y : int) : Boolean
		{
			if(this.m_noteMap[p_y] == null)
				return false;
			if(this.m_noteMap[p_y][p_x] == null)
				return false;
			return this.m_noteMap[p_y][p_x][NOTE_CLOSED];
		}

		/**
		 * @private
		 * 获取某节点的周围节点，排除不能通过和已在关闭列表中的
		 */
		public function getArounds(p_x : int , p_y : int) : Array
		{
			var arr : Array = [];
			var checkX : int;
			var checkY : int;
			var canDiagonal : Boolean;

			//右
			checkX = p_x + 1;
			checkY = p_y;
			var canRight : Boolean = (isBlock(checkX , checkY) == false);
			if(canRight && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//下
			checkX = p_x;
			checkY = p_y + 1;
			var canDown : Boolean = (isBlock(checkX , checkY) == false);
			if(canDown && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}

			//左
			checkX = p_x - 1;
			checkY = p_y;
			var canLeft : Boolean = (isBlock(checkX , checkY) == false);
			if(canLeft && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//上
			checkX = p_x;
			checkY = p_y - 1;
			var canUp : Boolean = (isBlock(checkX , checkY) == false);
			if(canUp && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//右下
			checkX = p_x + 1;
			checkY = p_y + 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal && canRight && canDown && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//左下
			checkX = p_x - 1;
			checkY = p_y + 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal && canLeft && canDown && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//左上
			checkX = p_x - 1;
			checkY = p_y - 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal && canLeft && canUp && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}
			//右上
			checkX = p_x + 1;
			checkY = p_y - 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal && canRight && canUp && !this.isClosed(checkX , checkY))
			{
				arr.push([checkX , checkY]);
			}

			return arr;
		}

		/**
		 * 获取周围所有可行走点的坐标
		 * @param p_x
		 * @param p_y
		 * @return
		 *
		 */
		public function getAroundsNoneBlock(p_x : int , p_y : int) : Array
		{
			var arr : Array = [];
			var checkX : int;
			var checkY : int;
			var canDiagonal : Boolean;

			//右
			checkX = p_x + 1;
			checkY = p_y;
			var canRight : Boolean = (isBlock(checkX , checkY) == false);
			if(canRight)
			{
				arr.push([checkX , checkY]);
			}
			//下
			checkX = p_x;
			checkY = p_y + 1;
			var canDown : Boolean = (isBlock(checkX , checkY) == false);
			if(canDown)
			{
				arr.push([checkX , checkY]);
			}

			//左
			checkX = p_x - 1;
			checkY = p_y;
			var canLeft : Boolean = (isBlock(checkX , checkY) == false);
			if(canLeft)
			{
				arr.push([checkX , checkY]);
			}
			//上
			checkX = p_x;
			checkY = p_y - 1;
			var canUp : Boolean = (isBlock(checkX , checkY) == false);
			if(canUp)
			{
				arr.push([checkX , checkY]);
			}
			//右下
			checkX = p_x + 1;
			checkY = p_y + 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal)
			{
				arr.push([checkX , checkY]);
			}
			//左下
			checkX = p_x - 1;
			checkY = p_y + 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal)
			{
				arr.push([checkX , checkY]);
			}
			//左上
			checkX = p_x - 1;
			checkY = p_y - 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal)
			{
				arr.push([checkX , checkY]);
			}
			//右上
			checkX = p_x + 1;
			checkY = p_y - 1;
			canDiagonal = (isBlock(checkX , checkY) == false);
			if(canDiagonal)
			{
				arr.push([checkX , checkY]);
			}

			return arr;
		}

		/**
		 * 取周围八向所有数据
		 * @param p_x
		 * @param p_y
		 * @return
		 *
		 */
		public function getAllArounds(p_x : int , p_y : int) : Array
		{
			var arr : Array = [];
			arr.push([p_x + 1 , p_y]);
			arr.push([p_x + 1 , p_y + 1]);
			arr.push([p_x + 1 , p_y - 1]);
			arr.push([p_x - 1 , p_y]);
			arr.push([p_x - 1 , p_y + 1]);
			arr.push([p_x - 1 , p_y - 1]);
			arr.push([p_x , p_y - 1]);
			arr.push([p_x , p_y + 1]);

			return arr;
		}

		/**
		 * 找到从 ［startIndexX ， startIndexY］ 到 ［endIndexX ， endIndexY］ 可用于寻路的最短的点
		 * @param startIndexX
		 * @param startIndexY
		 * @param endIndexX
		 * @param endIndexY
		 * @param closed
		 * @return
		 *
		 */
		public function getAvailablePoint(startIndexX : int , startIndexY : int , endIndexX : int , endIndexY : int , closed : Array = null) : Array
		{
			if(closed == null)
				closed = [];

			var avaliable : Array = null;
			if(isBlock(startIndexX , startIndexY))
			{
				closed.push(startIndexX + "_" + startIndexY);
				var arounds : Array = getAroundsNoneBlock(startIndexX , startIndexY);
				for each(var arr : Array in arounds)
				{
					if(!isBlock(arr[0] , arr[1]))
					{
						avaliable = [arr[0] , arr[1]];
						break;
					}
				}

				if(avaliable == null && arounds.length > 0)
				{
					for each(var toCheck : Array in arounds)
					{
						if(closed.indexOf(toCheck[0] + "_" + toCheck[1]) == -1)
						{
							var start2endDst : int = getDistance(startIndexX , startIndexY , endIndexX , endIndexY);
							var preDst : int = getDistance(toCheck[0] , toCheck[1] , endIndexX , endIndexY);
							if(preDst < start2endDst)
								break;
						}
					}
					avaliable = getAvailablePoint(toCheck[0] , toCheck[1] , endIndexX , endIndexY , closed);
				}
				else if(avaliable == null && arounds.length == 0)
				{
					Log.warning("周围没有一点是可以走的");
					var allArounds : Array = getAllArounds(startIndexX , startIndexY);
					start2endDst = getDistance(startIndexX , startIndexY , endIndexX , endIndexY);
					for each(toCheck in allArounds)
					{
						if(closed.indexOf(toCheck[0] + "_" + toCheck[1]) == -1)
						{
							preDst = getDistance(toCheck[0] , toCheck[1] , endIndexX , endIndexY);
							if(preDst < start2endDst)
								break;
						}
					}
					avaliable = getAvailablePoint(toCheck[0] , toCheck[1] , endIndexX , endIndexY , closed);
						//					var xPlusMinus : int = CommonUtil.getXPlusMinusByDir(_role.dir);
				}
			}

			closed = null;

			return avaliable == null ? [startIndexX , startIndexY] : avaliable;
		}

		/**
		 * 计算两点距离
		 * @param Ax	A点x坐标
		 * @param Ay	A点y坐标
		 * @param Bx	B点x坐标
		 * @param By	B点y坐标
		 */
		public function getDistance(Ax : int , Ay : int , Bx : int , By : int) : int
		{
			return (Math.sqrt(((Ax - Bx) * (Ax - Bx)) + ((Ay - By) * (Ay - By))));
		}

		/**
		 * @private
		 * 获取路径
		 *
		 * @param p_startX	起始点X坐标
		 * @param p_startY	起始点Y坐标
		 * @param p_id		终点的ID
		 *
		 * @return 			路径坐标(Point)数组
		 */
		private function getPath(p_startX : int , p_startY : int , p_id : int) : Array
		{
			var arr : Array = [];
			var noteX : int = this.m_xList[p_id];
			var noteY : int = this.m_yList[p_id];
			while(noteX != p_startX || noteY != p_startY)
			{
				arr.unshift([noteX , noteY]);
				p_id = this.m_fatherList[p_id];
				noteX = this.m_xList[p_id];
				noteY = this.m_yList[p_id];
			}
			arr.unshift([p_startX , p_startY]);
			var time : int = getTimer();
			arr = perfectPath(arr);
			arr = getDirectPath(arr);
//			Log.print("优化路径耗时:" + (getTimer() - time) + "ms");
			return arr;
		}

		/**
		 * 优化后的路径,只记录转节点数
		 * @param arr
		 * @return
		 *
		 */
		private function perfectPath(arr : Array) : Array
		{

			if(arr == null || arr.length < 3)
				return arr;
			var newArr : Array = [];
			//上一次的节点
			var lastNode : Array = arr[0];
			//上一次方向
			var lastFace : int = getPerfectFace(arr[1] , lastNode);
			//当前的方向
			var curface : int;
			//厂前节点
			var curNode : Array;
			newArr.push(lastNode);
			for(var i : int = 1 ; i < arr.length ; i++)
			{
				curNode = arr[i];
				curface = getPerfectFace(curNode , lastNode);
				//如果当前节点和上个节点不一样,责表示出现了拐点,记录上个节点
				if(curface != lastFace)
				{
					if(lastNode)
						newArr.push(lastNode);
					lastFace = curface;
				}
				lastNode = curNode;
			}
			newArr.push(lastNode);
			return newArr;
		}

		/**
		 * 获得当前节点和上个节点是否是同一个方向
		 */
		private function getPerfectFace(node : Array , lastNode : Array) : int
		{
			return (node[1] - lastNode[1]) * 10 + (node[0] - lastNode[0]);
		}

		/**
		 * 获得优化后的直线路径
		 * @param arr
		 * @return
		 *
		 */
		public function getDirectPath(arr : Array = null) : Array
		{
			if(arr == null)
				return null;
			var len : uint = arr.length;
			//3个点一下直接返回
			if(len < 3)
				return arr;
			var directArr : Array = [];
			var startNode : Array = arr[0];
			var endNode : Array = arr[len - 1];
			var index : uint = 0;
			directArr.push(startNode);
			while(startNode != endNode)
			{

				for(var i : int = len - 1 ; i > index ; i--)
				{
					var curNode : Array = arr[i];
					//最后一个节点直接写进入..因为后面没有可以搜索的节点了
					var isEnd : Boolean = Boolean((i - index) == 1);
					if(isEnd || isThroughPath(startNode , curNode))
					{
						index = i;
						startNode = curNode;
						directArr.push(curNode);
						break;
					}
				}
			}
			return directArr;
		}

		//是否x轴是一条直线,判断2点Y坐标
		private var isDirectX : Boolean;
		//是否y轴是一条直线,判断2点X坐标
		private var isDirectY : Boolean;
		private var directXValue : int;
		private var directYValue : int;
		private var k : Number;
		private var b : Number;
		//当前穿过的节点
		private var curNode : Array;

		private function isThroughPath(s : Array , e : Array) : Boolean
		{
			if(s == null || e == null)
				return false;
			isDirectX = s[1] == e[1];
			isDirectY = s[0] == e[0];
			//直线方程
			k = ((e[1] - s[1]) * titleHeight) / ((e[0] - s[0]) * titleWidth);
			b = (e[1] + 0.5) * titleHeight - (((e[0] + 0.5) * titleWidth) * k);

			if(isDirectX)
				directXValue = s.y * titleHeight;
			if(isDirectY)
				directYValue = s.x * titleWidth;

			var minx : int = Math.min(e[0] , s[0]);
			var maxx : int = Math.max(e[0] , s[0]);
			var miny : int = Math.min(s[1] , e[1]);
			var maxy : int = Math.max(s[1] , e[1]);

			var startPx : int = (minx + 0.5) * titleWidth;
			var endPx : int = (maxx + 0.5) * titleWidth;
			var startPy : int = (miny + 0.5) * titleHeight;
			var endPy : int = (maxy + 0.5) * titleHeight;

			var px : int;
			var py : int;
			curNode = s[0] < e[0] ? s : e;
			var i : int;
			for(i = minx ; i <= maxx ; i++)
			{
				px = i * titleWidth + 1;
				if(px >= startPx && px <= endPx)
				{
					py = getPy(px);
					if(!checkIsThroughCurNode(px , py))
						return false;
				}

				px = (i + 1) * titleWidth - 1;
				if(px >= startPx && px <= endPx)
				{
					py = getPy(px);
					if(!checkIsThroughCurNode(px , py))
						return false;
				}
			}

			curNode = s[1] < e[1] ? s : e;
			for(i = miny ; i <= maxy ; i++)
			{
				py = i * titleHeight + 1;
				if(py >= startPy && py <= endPy)
				{
					px = getPx(py);
					if(!checkIsThroughCurNode(px , py))
						return false;
				}

				py = (i + 1) * titleHeight - 1;
				if(py >= startPy && py <= endPy)
				{
					px = getPx(py);
					if(!checkIsThroughCurNode(px , py))
						return false;
				}
			}
			return true;
		}

		/**
		 * 检查时候穿过这个节点
		 * @param curNode
		 * @return
		 *
		 */
		private function checkIsThroughCurNode(px : int , py : int) : Boolean
		{
			curNode = GameUtils.getGridByPixel(px , py);
			if(isBlock(curNode[0] , curNode[1]))
				return false;
			if(checkCorner(curNode))
				return false;
			return true;
		}

		private function checkCorner(n : Array) : Boolean
		{
			var face : int = getface(n);
			var c1 : Array;
			var c2 : Array;
			switch(face)
			{
				case 4:
					c1 = _mapBlocks[n[1]][n[0] - 1];
					c2 = _mapBlocks[n[1] - 1][n[0]];
					break;
				case -2:
					c1 = _mapBlocks[n[1]][n[0] - 1];
					c2 = _mapBlocks[n[1] + 1][n[0]];
					break;
				case -4:
					c1 = _mapBlocks[n[1]][n[0] + 1];
					c2 = _mapBlocks[n[1] + 1][n[0]];
					break;
				case 2:
					c1 = _mapBlocks[n[1]][n[0] + 1];
					c2 = _mapBlocks[n[1] + 1][n[0]];
					break;
				default:
					return false;
					break;
			}
			if(isBlock(c1[0] , c1[1]) && isBlock(c2[0] , c2[1]))
				return true;
			return false;
		}

		private function getface(n : Array) : int
		{
			var result : int = (n[1] - curNode[1]) * 3 + (n[0] - curNode[0]);
			return result;
		}

		/**
		 * 根据Y坐标算出所对应直线的X坐标
		 * @param y
		 * @return
		 *
		 */
		private function getPx(y : Number) : Number
		{
			if(isDirectY)
				return directYValue;
			return (y - b) / k;
		}

		/**
		 * 根据X坐标算出所对应直线的Y坐标
		 * @param y
		 * @return
		 *
		 */
		private function getPy(x : Number) : Number
		{
			if(isDirectX)
				return directXValue;
			return k * x + b;
		}

		/**
		 * @private
		 * 获取某ID节点在开放列表中的索引(从1开始)
		 */
		private function getIndex(p_id : int) : int
		{
			var i : int = 1;
			for each(var id : int in this.m_openList)
			{
				if(id == p_id)
				{
					return i;
				}
				i++;
			}
			return -1;
		}

		/**
		 * @private
		 * 获取某节点的路径评分
		 *
		 * @param p_index	节点在开启列表中的索引(从1开始)
		 */
		private function getScore(p_index : int) : int
		{
			return this.m_pathScoreList[this.m_openList[p_index - 1]];
		}

		/**
		 * @private
		 * 初始化数组
		 */
		private function initLists() : void
		{
			this.m_openList.length = 0; //=  new Vector.<int>();
			this.m_xList.length = 0; // = new Vector.<int>();
			this.m_yList.length = 0; // = new Vector.<int>();
			this.m_pathScoreList.length = 0; // = new Vector.<int>();
			this.m_movementCostList.length = 0; // = new Vector.<int>();
			this.m_fatherList.length = 0; // = new Vector.<int>();
			this.m_noteMap = [];
		}

		/**
		 * @private
		 * 销毁数组
		 */
		private function destroyLists() : void
		{
//			this.m_openList = null;
//			this.m_xList = null;
//			this.m_yList = null;
//			this.m_pathScoreList = null;
//			this.m_movementCostList = null;
//			this.m_fatherList = null;
//			this.m_noteMap = null;
		}
	}
}